package cn.hycat.leetcode.middle;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
//34. 在排序数组中查找元素的第一个和最后一个位置
//        给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
//
//        如果数组中不存在目标值 target，返回 [-1, -1]。
//
//        进阶：
//
//        你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
//        示例 1：
//
//        输入：nums = [5,7,7,8,8,10], target = 8
//        输出：[3,4]
public class L34在排序数组中查找元素的第一个和最后一个位置 {
    public int[] searchRange(int[] nums, int target) {
        int[] a = {-1,-1};
        if(nums.length == 0) return a;
        //nums = [5,7,7,8,8,10] 找大于(8 - 1)的第一个索引
        int n = binary_search(nums, target - 1);
        //nums = [5,7,7,8,8,10] 找大于8的第一个索引 - 1
        int m = binary_search(nums, target) - 1;
        if(n <= m && n >= 0 && m < nums.length) {
            a[0] = n;
            a[1] = m;
        }
        return a;
    }

    //二分查找第一个大于target的索引
    public int binary_search(int[] nums ,int target) {
        int l = 0, r = nums.length - 1;
        int ans = nums.length;
        while(l <= r) {
            int m = l +((r - l) >> 1);
            if(nums[m] > target) {
                ans = Math.min(ans, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }
}
